package com.model;

import java.awt.*;
import java.awt.event.MouseAdapter;
import java.awt.event.MouseEvent;

import javax.swing.*;


import java.util.*;
import java.lang.Math;
import java.util.List;
import java.util.concurrent.*;
import java.util.concurrent.atomic.AtomicInteger;

public class Draw{
    public static void main(String[] args) {
        new DrawSee();
    }
}

class DrawSee extends JFrame {

    public int boardWidth = 9;
    public int boardHeight = 10;
	public Game game = new Game();

    public int offset = 60;
	public int geziWidth = 20;

    public Container conn;
    private Graphics jg;

    public DrawSee() {
        conn = this.getContentPane();
        setBounds(10, 10, offset+geziWidth*(boardWidth+1)+40, offset+geziWidth*(boardWidth+1)+40+60);
        setVisible(true);
        conn.setBackground(new Color(255,255,255));
        setLayout(null);
        setResizable(false);
        this.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);

        Container conn = this.getContentPane();
        JButton btn1 = new JButton("pass");
        btn1.setBounds(10,offset+geziWidth*boardWidth+30,100,30);
        conn.add(btn1);

        try {
            Thread.sleep(500);
        } catch (Exception e) {
            e.printStackTrace();
        }

        jg =  this.getGraphics();
		drawState(game.curState);

		Game curGame = this.game;
        this.addMouseListener(new MouseAdapter() {


            public void mouseReleased(MouseEvent e) {

                int xm = e.getX(), ym = e.getY();

				float canvasX = xm - offset;
				float canvasY = ym - offset;

                int x = Math.round(canvasX / (float)geziWidth);
                int y = Math.round(canvasY / (float)geziWidth);

                if(x < 0 || x >= boardWidth || y < 0 || y >= boardHeight) {
					return;
				}

                Cell c = game.curState.cellMap.getOrDefault(game.curState.xy2idx(x,y), new Cell("none",-1,-1,0,null,-1));

                if(c.color==game.curColor) {
                    curGame.selectedCell = c;
                    curGame.selected = true;
                }else{
                    if(curGame.selected){
                        game.placePiece(curGame.selectedCell, x, y);
                        game.selected = false;
                    }
                }

				drawState(game.curState);

            }

        });

//        this.playAuto();

    }

    public void playAuto(){
        while (this.game.curState.winColor==0){
            Node node = new Node(null,this.game.curState);
            if(this.game.curState.lastMove.color==-1){
                node.getScoreMultithreading();
            }else {
                node.getScoreMultithreading();
            }

            Node bestChild = node.bestChild;
            if(bestChild!=null){
                System.out.println("score: " + bestChild.score);
                this.game.curState = bestChild.state;
                game.node = bestChild;
                this.drawState(this.game.curState);
                if(this.game.curState.winColor!=0){
                    System.out.println("winner: " + this.game.curState.winColor);
                    this.game.reset();
                }
            }
        }
    }

    public void clearDesk(){
		try {
            jg.setColor(new Color(255,255,255));
            jg.fillRect(0,0, 800, offset+geziWidth*(boardHeight+1)+40);
            jg.setColor(new Color(250,190,70));
            jg.fillRect(offset-geziWidth/2, offset-geziWidth/2, geziWidth*boardWidth, geziWidth*boardHeight);
			jg.setColor(Color.black);
            for(int i = 0; i < boardWidth; i ++) {
                jg.drawLine(i * geziWidth+offset,offset,i * geziWidth+offset,offset+geziWidth * (boardHeight-1));
			}
            for(int i = 0; i < boardHeight; i ++) {
                jg.drawLine(offset,offset+geziWidth * i,offset+geziWidth * (boardWidth-1),offset+geziWidth * i);
            }


        } catch (Exception e) {
            e.printStackTrace();
        }
	}

	public void drawPiece(Cell cell){
		try {
			if(cell.color == 1) {
				jg.setColor(Color.red);
			} else {
				jg.setColor(Color.black);
			}
			jg.drawArc(offset+geziWidth*cell.x-geziWidth/2,offset+geziWidth*cell.y-geziWidth/2,geziWidth,geziWidth,0,360);
			String str = Cell.type2String(cell.type);
			this.drawCenteredString(jg, str, new Rectangle(offset+geziWidth*cell.x-geziWidth/2,offset+geziWidth*cell.y-geziWidth/2,geziWidth,geziWidth));
        } catch (Exception e) {
            e.printStackTrace();
        }
	}

    public void drawCenteredString(Graphics g, String text, Rectangle rect) {
        // Get the FontMetrics
        FontMetrics metrics = g.getFontMetrics(g.getFont());
        // Determine the X coordinate for the text
        int x = rect.x + (rect.width - metrics.stringWidth(text)) / 2;
        // Determine the Y coordinate for the text (note we add the ascent, as in java 2d 0 is top of the screen)
        int y = rect.y + ((rect.height - metrics.getHeight()) / 2) + metrics.getAscent();
        // Draw the String
        g.drawString(text, x, y);
    }

	public void drawSelected(Cell cell){
        jg.setColor(Color.green);
        jg.drawRect(offset+geziWidth*cell.x-geziWidth/2,offset+geziWidth*cell.y-geziWidth/2,geziWidth,geziWidth);
	}

    public void drawLegalMoves(int x,int y,int color){
        try {
            if(color == 1) {
                jg.setColor(new Color(50,50,50));
            } else {
                jg.setColor(new Color(200,200,200));
            }
            jg.drawArc(offset+geziWidth*x+geziWidth/4,offset+geziWidth*y+geziWidth/4,geziWidth/2,geziWidth/2,0,360);
        } catch (Exception e) {
            e.printStackTrace();
        }
    }

	public void drawState(State state){
		try {
			clearDesk();
			HashMap<Integer, Cell> cellMap = state.cellMap;
			cellMap.forEach((idx, cell)->{
				drawPiece(cell);
			});
			if(game.selected){
			    drawSelected(game.selectedCell);
            }
            if(game.curState.lastMove.color!=0){
                drawSelected(game.curState.lastMove);
            }
        } catch (Exception e) {
            e.printStackTrace();
        }

        this.drawInfo();
	}

    public void drawInfo(){
        try {
            jg.setColor(new Color(0,0,0));
            String white = "white:(" + game.curState.lastMove.x + "," + game.curState.lastMove.y+ ")";
			jg.drawString(white, 10, offset + geziWidth*(boardWidth+1));
            String rate = "rate: " + (float)game.node.Q/(float)game.node.N;
			jg.drawString(rate, 10, offset + geziWidth*(boardWidth+1) + 20);

            if(game.winColor!=0){
                String winColor = "winColor: " + game.winColor;
			    jg.drawString(winColor, 10+100, offset + geziWidth*(boardWidth+1));
            }
        } catch (Exception e) {
            e.printStackTrace();
        }
    }

}

class Game{
	public int curColor;
	public int boardWidth = 9;
	public int boardHeight = 10;
	public State curState;
    public Node node;
    public int winColor = 0;
    public Cell selectedCell;
    public boolean selected = false;

    public void reset(){
        this.curColor = 1;
        this.curState = new State(null);

        Cell[] cells = new Cell[]{
                new Cell("bing",0,6,1,this.curState,this.curState.xy2idx(0,6)),
                new Cell("bing",2,6,1,this.curState,this.curState.xy2idx(2,6)),
                new Cell("bing",4,6,1,this.curState,this.curState.xy2idx(4,6)),
                new Cell("bing",6,6,1,this.curState,this.curState.xy2idx(6,6)),
                new Cell("bing",8,6,1,this.curState,this.curState.xy2idx(8,6)),
                new Cell("pao",1,7,1,this.curState,this.curState.xy2idx(1,7)),
                new Cell("pao",7,7,1,this.curState,this.curState.xy2idx(7,7)),
                new Cell("che",0,9,1,this.curState,this.curState.xy2idx(0,9)),
                new Cell("che",8,9,1,this.curState,this.curState.xy2idx(8,9)),
                new Cell("ma",1,9,1,this.curState,this.curState.xy2idx(1,9)),
                new Cell("ma",7,9,1,this.curState,this.curState.xy2idx(7,9)),
                new Cell("xiang",2,9,1,this.curState,this.curState.xy2idx(2,9)),
                new Cell("xiang",6,9,1,this.curState,this.curState.xy2idx(6,9)),
                new Cell("shi",3,9,1,this.curState,this.curState.xy2idx(3,9)),
                new Cell("shi",5,9,1,this.curState,this.curState.xy2idx(5,9)),
                new Cell("jiang",4,9,1,this.curState,this.curState.xy2idx(4,9)),
                new Cell("bing",0,3,-1,this.curState,this.curState.xy2idx(0,3)),
                new Cell("bing",2,3,-1,this.curState,this.curState.xy2idx(2,3)),
                new Cell("bing",4,3,-1,this.curState,this.curState.xy2idx(4,3)),
                new Cell("bing",6,3,-1,this.curState,this.curState.xy2idx(6,3)),
                new Cell("bing",8,3,-1,this.curState,this.curState.xy2idx(8,3)),
                new Cell("pao",1,2,-1,this.curState,this.curState.xy2idx(1,2)),
                new Cell("pao",7,2,-1,this.curState,this.curState.xy2idx(7,2)),
                new Cell("che",0,0,-1,this.curState,this.curState.xy2idx(0,0)),
                new Cell("che",8,0,-1,this.curState,this.curState.xy2idx(8,0)),
                new Cell("ma",1,0,-1,this.curState,this.curState.xy2idx(1,0)),
                new Cell("ma",7,0,-1,this.curState,this.curState.xy2idx(7,0)),
                new Cell("xiang",2,0,-1,this.curState,this.curState.xy2idx(2,0)),
                new Cell("xiang",6,0,-1,this.curState,this.curState.xy2idx(6,0)),
                new Cell("shi",3,0,-1,this.curState,this.curState.xy2idx(3,0)),
                new Cell("shi",5,0,-1,this.curState,this.curState.xy2idx(5,0)),
                new Cell("jiang",4,0,-1,this.curState,this.curState.xy2idx(4,0))
        };

        curState.cellMap.clear();
        for (int i = 0; i < cells.length; i++) {
            curState.cellMap.put(cells[i].idx,cells[i]);
        }
        for (int i = 0; i < cells.length; i++) {
            cells[i].initNextCoordList();
        }

        this.curState.lastMove = new Cell("none",-1,-1,-1,null,-1);
        this.node = new Node(null,this.curState);

        this.winColor = 0;
        this.selected = false;
        this.selectedCell = null;
    }

    Game() {
        this.reset();
    }

    public void placePiece(Cell cell, int x, int y){
        Cell c = this.curState.checkPiece(cell, x, y);

        if(!c.type.equals("illegal")){

            this.curState.placePiece(cell, x, y);

            if(this.curState.winColor!=0){
                System.out.println("winner: " + this.curState.winColor);
                this.reset();
            }

            this.curColor = -this.curColor;

            Node node = new Node(null,this.curState);

            long startTime = System.currentTimeMillis();
//            node.getScore(3);
            node.getScoreMultithreading();
            long endTime = System.currentTimeMillis();
            System.out.println("耗时：" + (endTime-startTime)/1000.0+"秒");
            Node bestChild = node.bestChild;

            if(bestChild!=null){
                this.curState = bestChild.state;
                this.curColor = -this.curColor;
                this.node = bestChild;

                if(this.curState.winColor!=0){
                    System.out.println("winner: " + this.curState.winColor);
                    this.reset();
                }
            }

        }
    }

    public void playBy2AI(){
        while (this.winColor==0){
            Node node = new Node(null,this.curState);
            node.getScore(3);
            Node bestChild = node.bestChild;
            if(bestChild!=null){
                this.curState = bestChild.state;
                this.node = bestChild;
                if(this.curState.winColor!=0){
                    System.out.println("winner: " + this.curState.winColor);
                    this.reset();
                }
            }
        }
    }

}

class Cell{

	public int x;
	public int y;
	public String type;
	public int color;
	public State state;
	public int idx;
	public ArrayList<int[]> nextCoordList = new ArrayList<>();
	public int score;
	public static HashMap<Integer, Integer> positionScoreBing;
	public static HashMap<Integer, Integer> positionScoreChe;
	public static HashMap<Integer, Integer> positionScoreMa;
	public static HashMap<Integer, Integer> positionScorePao;
	static {
        positionScoreBing = new HashMap<>();
        int[] sbing = new int[]{
                0,3,6,9,12,9,6,3,0,
                18,36,56,80,120,80,56,36,18,
                14,26,42,60,80,60,42,26,14,
                10,20,30,34,40,34,30,20,10,
                6,12,18,18,20,18,18,12,6,
                2,0,8,0,8,0,8,0,2,
                0,0,-2,0,4,0,-2,0,0,
                0,0,0,0,0,0,0,0,0,
                0,0,0,0,0,0,0,0,0,
                0,0,0,0,0,0,0,0,0
        };
        for (int i = 0; i < sbing.length; i++) {
            positionScoreBing.put(i,sbing[i]);
        }

        positionScoreChe = new HashMap<>();
        int[] sche = new int[]{
                14,14,12,18,16,18,12,14,14,
                16,20,18,24,26,24,18,20,16,
                12,12,12,18,18,18,12,12,12,
                12,18,16,22,22,22,16,18,12,
                12,14,12,18,18,18,12,14,12,
                12,16,14,20,20,20,14,16,12,
                6,10,8,14,14,14,8,10,6,
                4,8,6,14,12,14,6,8,4,
                8,4,8,16,8,16,8,4,8,
                -2,10,6,14,12,14,6,10,-2
        };
        for (int i = 0; i < sche.length; i++) {
            positionScoreChe.put(i,sche[i]);
        }

        positionScoreMa = new HashMap<>();
        int[] sma = new int[]{
                4,8,16,12,4,12,16,8,4,
                4,10,28,16,8,16,28,10,4,
                12,14,16,20,18,20,16,14,12,
                8,24,18,24,20,24,18,24,8,
                6,16,14,18,16,18,14,16,6,
                4,12,16,14,12,14,16,12,4,
                2,6,8,6,10,6,8,6,2,
                4,2,8,8,4,8,8,2,4,
                0,2,4,4,-2,4,4,2,0,
                0,-4,0,0,0,0,0,-4,0
        };
        for (int i = 0; i < sma.length; i++) {
            positionScoreMa.put(i,sma[i]);
        }

        positionScorePao = new HashMap<>();
        int[] spao = new int[]{
                6,4,0,-10,-12,-10,0,4,6,
                2,2,0,-4,-14,-4,0,2,2,
                2,2,0,-10,-8,-10,0,2,2,
                0,0,-2,4,10,4,-2,0,0,
                0,0,0,2,8,2,0,0,0,
                -2,0,4,2,6,2,4,0,-2,
                0,0,0,2,4,2,0,0,0,
                4,0,8,6,10,6,8,0,4,
                0,2,4,6,6,6,4,2,0,
                0,0,2,6,6,6,2,0,0
        };
        for (int i = 0; i < spao.length; i++) {
            positionScorePao.put(i,spao[i]);
        }
    }

	Cell(String type, int x, int y, int color, State state, int idx) {
		this.type = type;
		this.x = x;
		this.y = y;
		this.color = color;
		this.state = state;
		this.idx = idx;
		this.initScore();
	}

    public static String type2String(String type) {
        if(type.equals("bing")){
            return "兵";
        }else if(type.equals("pao")){
            return "炮";
        }else if(type.equals("che")){
            return "车";
        }else if(type.equals("ma")){
            return "马";
        }else if(type.equals("xiang")){
            return "象";
        }else if(type.equals("shi")){
            return "士";
        }else if(type.equals("jiang")){
            return "将";
        }

        return "";
    }

    public Cell clone(){
	    Cell cell = new Cell(this.type,this.x,this.y,this.color,this.state,this.idx);
	    cell.score = this.score;
	    cell.nextCoordList = new ArrayList<>(this.nextCoordList);
	    return cell;
    }

    public void initScore() {
	    if(this.type.equals("bing")){
	        this.score = 70;
        }else if(this.type.equals("pao")){
            this.score = 300;
        }else if(this.type.equals("che")){
            this.score = 600;
        }else if(this.type.equals("ma")){
            this.score = 300;
        }else if(this.type.equals("xiang")){
            this.score = 110;
        }else if(this.type.equals("shi")){
            this.score = 110;
        }else if(this.type.equals("jiang")){
            this.score = Node.JiangScore;
        }
    }

    public int getPositionScore() {
        if(this.type.equals("bing")){
            if(this.color==1){
                return Cell.positionScoreBing.get(this.idx);
            }else if(this.color==-1) {
                return Cell.positionScoreBing.get(State.xy2idx(this.x,State.boardHeight-1-this.y));
            }
        }else if(this.type.equals("pao")){
            if(this.color==1){
                return Cell.positionScorePao.get(this.idx);
            }else if(this.color==-1) {
                return Cell.positionScorePao.get(State.xy2idx(this.x,State.boardHeight-1-this.y));
            }
        }else if(this.type.equals("che")){
            if(this.color==1){
                return Cell.positionScoreChe.get(this.idx);
            }else if(this.color==-1) {
                return Cell.positionScoreChe.get(State.xy2idx(this.x,State.boardHeight-1-this.y));
            }
        }else if(this.type.equals("ma")){
            if(this.color==1){
                return Cell.positionScoreMa.get(this.idx);
            }else if(this.color==-1) {
                return Cell.positionScoreMa.get(State.xy2idx(this.x,State.boardHeight-1-this.y));
            }
        }

        return 0;
    }

    public void initNextCoordList(){
	    this.nextCoordList.clear();
        if(this.type.equals("bing")){

            if(this.color==1){
                if(this.y-1>=0){
                    Cell c = this.state.cellMap.getOrDefault(State.xy2idx(this.x,this.y-1), new Cell("none",-1,-1,0,null,-1));
                    if(c.color!=this.color){
                        nextCoordList.add(new int[]{this.x,this.y-1});
                    }
                }
                if(this.y<5){
                    if(this.x-1>=0){
                        Cell c = this.state.cellMap.getOrDefault(State.xy2idx(this.x-1,this.y), new Cell("none",-1,-1,0,null,-1));
                        if(c.color!=this.color){
                            nextCoordList.add(new int[]{this.x-1,this.y});
                        }
                    }
                    if(this.x+1<this.state.boardWidth){
                        Cell c = this.state.cellMap.getOrDefault(State.xy2idx(this.x+1,this.y), new Cell("none",-1,-1,0,null,-1));
                        if(c.color!=this.color){
                            nextCoordList.add(new int[]{this.x+1,this.y});
                        }
                    }
                }

            }else if(this.color==-1){
                if(this.y+1<this.state.boardHeight){
                    Cell c = this.state.cellMap.getOrDefault(State.xy2idx(this.x,this.y+1), new Cell("none",-1,-1,0,null,-1));
                    if(c.color!=this.color){
                        nextCoordList.add(new int[]{this.x,this.y+1});
                    }
                }
                if(this.y>4){
                    if(this.x-1>=0){
                        Cell c = this.state.cellMap.getOrDefault(State.xy2idx(this.x-1,this.y), new Cell("none",-1,-1,0,null,-1));
                        if(c.color!=this.color){
                            nextCoordList.add(new int[]{this.x-1,this.y});
                        }
                    }
                    if(this.x+1<this.state.boardWidth){
                        Cell c = this.state.cellMap.getOrDefault(State.xy2idx(this.x+1,this.y), new Cell("none",-1,-1,0,null,-1));
                        if(c.color!=this.color){
                            nextCoordList.add(new int[]{this.x+1,this.y});
                        }
                    }
                }

            }
        }else if(this.type.equals("pao")){
            //up
            int y = this.y-1;
            for (; y >= 0; y--) {
                Cell c = this.state.cellMap.getOrDefault(State.xy2idx(this.x,y), new Cell("none",-1,-1,0,null,-1));
                if(c.color==0){
                    nextCoordList.add(new int[]{this.x,y});
                }else {
                    break;
                }
            }
            y--;
            for (; y >= 0; y--) {
                Cell c = this.state.cellMap.getOrDefault(State.xy2idx(this.x,y), new Cell("none",-1,-1,0,null,-1));
                if(c.color==this.color){
                    break;
                }
                if(c.color==-this.color){
                    nextCoordList.add(new int[]{this.x,y});
                    break;
                }
            }

            //down
            for (y = this.y+1; y < this.state.boardHeight; y++) {
                Cell c = this.state.cellMap.getOrDefault(State.xy2idx(this.x,y), new Cell("none",-1,-1,0,null,-1));
                if(c.color==0){
                    nextCoordList.add(new int[]{this.x,y});
                }else {
                    break;
                }
            }
            y++;
            for (; y < this.state.boardHeight; y++) {
                Cell c = this.state.cellMap.getOrDefault(State.xy2idx(this.x,y), new Cell("none",-1,-1,0,null,-1));
                if(c.color==this.color){
                    break;
                }
                if(c.color==-this.color){
                    nextCoordList.add(new int[]{this.x,y});
                    break;
                }
            }

            //left
            int x = this.x-1;
            for (; x >= 0; x--) {
                Cell c = this.state.cellMap.getOrDefault(State.xy2idx(x,this.y), new Cell("none",-1,-1,0,null,-1));
                if(c.color==0){
                    nextCoordList.add(new int[]{x,this.y});
                }else {
                    break;
                }
            }
            x--;
            for (; x >= 0; x--) {
                Cell c = this.state.cellMap.getOrDefault(State.xy2idx(x,this.y), new Cell("none",-1,-1,0,null,-1));
                if(c.color==this.color){
                    break;
                }
                if(c.color==-this.color){
                    nextCoordList.add(new int[]{x,this.y});
                    break;
                }
            }

            //right
            for (x = this.x+1; x < this.state.boardWidth; x++) {
                Cell c = this.state.cellMap.getOrDefault(State.xy2idx(x,this.y), new Cell("none",-1,-1,0,null,-1));
                if(c.color==0){
                    nextCoordList.add(new int[]{x,this.y});
                }else {
                    break;
                }
            }
            x++;
            for (; x < this.state.boardWidth; x++) {
                Cell c = this.state.cellMap.getOrDefault(State.xy2idx(x,this.y), new Cell("none",-1,-1,0,null,-1));
                if(c.color==this.color){
                    break;
                }
                if(c.color==-this.color){
                    nextCoordList.add(new int[]{x,this.y});
                    break;
                }
            }
        }else if(this.type.equals("che")){
            //up
            int y = this.y-1;
            for (; y >= 0; y--) {
                Cell c = this.state.cellMap.getOrDefault(State.xy2idx(this.x,y), new Cell("none",-1,-1,0,null,-1));
                if(c.color==0){
                    nextCoordList.add(new int[]{this.x,y});
                }else {
                    if(c.color!=this.color){
                        nextCoordList.add(new int[]{this.x,y});
                    }
                    break;
                }
            }

            //down
            y = this.y+1;
            for (; y < this.state.boardHeight; y++) {
                Cell c = this.state.cellMap.getOrDefault(State.xy2idx(this.x,y), new Cell("none",-1,-1,0,null,-1));
                if(c.color==0){
                    nextCoordList.add(new int[]{this.x,y});
                }else {
                    if(c.color!=this.color){
                        nextCoordList.add(new int[]{this.x,y});
                    }
                    break;
                }
            }

            //left
            int x = this.x-1;
            for (; x >= 0; x--) {
                Cell c = this.state.cellMap.getOrDefault(State.xy2idx(x,this.y), new Cell("none",-1,-1,0,null,-1));
                if(c.color==0){
                    nextCoordList.add(new int[]{x,this.y});
                }else {
                    if(c.color!=this.color){
                        nextCoordList.add(new int[]{x,this.y});
                    }
                    break;
                }
            }

            //right
            x = this.x+1;
            for (; x < this.state.boardWidth; x++) {
                Cell c = this.state.cellMap.getOrDefault(State.xy2idx(x,this.y), new Cell("none",-1,-1,0,null,-1));
                if(c.color==0){
                    nextCoordList.add(new int[]{x,this.y});
                }else {
                    if(c.color!=this.color){
                        nextCoordList.add(new int[]{x,this.y});
                    }
                    break;
                }
            }
        }else if(this.type.equals("ma")){
            if(this.y-2>=0){
                Cell c = this.state.cellMap.getOrDefault(State.xy2idx(this.x,this.y-1), new Cell("none",-1,-1,0,null,-1));
                if(c.color==0){
                    if(this.x-1>=0){
                        Cell c1 = this.state.cellMap.getOrDefault(State.xy2idx(this.x-1,this.y-2), new Cell("none",-1,-1,0,null,-1));
                        if(c1.color!=this.color){
                            nextCoordList.add(new int[]{this.x-1,this.y-2});
                        }
                    }
                    if(this.x+1<this.state.boardWidth){
                        Cell c1 = this.state.cellMap.getOrDefault(State.xy2idx(this.x+1,this.y-2), new Cell("none",-1,-1,0,null,-1));
                        if(c1.color!=this.color){
                            nextCoordList.add(new int[]{this.x+1,this.y-2});
                        }
                    }
                }
            }

            if(this.y+2<this.state.boardHeight){
                Cell c = this.state.cellMap.getOrDefault(State.xy2idx(this.x,this.y+1), new Cell("none",-1,-1,0,null,-1));
                if(c.color==0){
                    if(this.x-1>=0){
                        Cell c1 = this.state.cellMap.getOrDefault(State.xy2idx(this.x-1,this.y+2), new Cell("none",-1,-1,0,null,-1));
                        if(c1.color!=this.color){
                            nextCoordList.add(new int[]{this.x-1,this.y+2});
                        }
                    }
                    if(this.x+1<this.state.boardWidth){
                        Cell c1 = this.state.cellMap.getOrDefault(State.xy2idx(this.x+1,this.y+2), new Cell("none",-1,-1,0,null,-1));
                        if(c1.color!=this.color){
                            nextCoordList.add(new int[]{this.x+1,this.y+2});
                        }
                    }
                }
            }

            if(this.x-2>=0){
                Cell c = this.state.cellMap.getOrDefault(State.xy2idx(this.x-1,this.y), new Cell("none",-1,-1,0,null,-1));
                if(c.color==0){
                    if(this.y-1>=0){
                        Cell c1 = this.state.cellMap.getOrDefault(State.xy2idx(this.x-2,this.y-1), new Cell("none",-1,-1,0,null,-1));
                        if(c1.color!=this.color){
                            nextCoordList.add(new int[]{this.x-2,this.y-1});
                        }
                    }
                    if(this.y+1<this.state.boardHeight){
                        Cell c1 = this.state.cellMap.getOrDefault(State.xy2idx(this.x-2,this.y+1), new Cell("none",-1,-1,0,null,-1));
                        if(c1.color!=this.color){
                            nextCoordList.add(new int[]{this.x-2,this.y+1});
                        }
                    }
                }
            }

            if(this.x+2<this.state.boardWidth){
                Cell c = this.state.cellMap.getOrDefault(State.xy2idx(this.x+1,this.y), new Cell("none",-1,-1,0,null,-1));
                if(c.color==0){
                    if(this.y-1>=0){
                        Cell c1 = this.state.cellMap.getOrDefault(State.xy2idx(this.x+2,this.y-1), new Cell("none",-1,-1,0,null,-1));
                        if(c1.color!=this.color){
                            nextCoordList.add(new int[]{this.x+2,this.y-1});
                        }
                    }
                    if(this.y+1<this.state.boardHeight){
                        Cell c1 = this.state.cellMap.getOrDefault(State.xy2idx(this.x+2,this.y+1), new Cell("none",-1,-1,0,null,-1));
                        if(c1.color!=this.color){
                            nextCoordList.add(new int[]{this.x+2,this.y+1});
                        }
                    }
                }
            }
        }else if(this.type.equals("xiang")){
            if(this.color==1){
                if(this.y-2>4){
                    if(this.x-2>=0){
                        Cell c1 = this.state.cellMap.getOrDefault(State.xy2idx(this.x-2,this.y-2), new Cell("none",-1,-1,0,null,-1));
                        if(c1.color!=this.color){
                            Cell c2 = this.state.cellMap.getOrDefault(State.xy2idx(this.x-1,this.y-1), new Cell("none",-1,-1,0,null,-1));
                            if(c2.color==0){
                                nextCoordList.add(new int[]{this.x-2,this.y-2});
                            }
                        }
                    }
                    if(this.x+2<this.state.boardWidth){
                        Cell c1 = this.state.cellMap.getOrDefault(State.xy2idx(this.x+2,this.y-2), new Cell("none",-1,-1,0,null,-1));
                        if(c1.color!=this.color){
                            Cell c2 = this.state.cellMap.getOrDefault(State.xy2idx(this.x+1,this.y-1), new Cell("none",-1,-1,0,null,-1));
                            if(c2.color==0){
                                nextCoordList.add(new int[]{this.x+2,this.y-2});
                            }
                        }
                    }
                }
                if(this.y+2<this.state.boardHeight){
                    if(this.x-2>=0){
                        Cell c1 = this.state.cellMap.getOrDefault(State.xy2idx(this.x-2,this.y+2), new Cell("none",-1,-1,0,null,-1));
                        if(c1.color!=this.color){
                            Cell c2 = this.state.cellMap.getOrDefault(State.xy2idx(this.x-1,this.y+1), new Cell("none",-1,-1,0,null,-1));
                            if(c2.color==0){
                                nextCoordList.add(new int[]{this.x-2,this.y+2});
                            }
                        }
                    }
                    if(this.x+2<this.state.boardWidth){
                        Cell c1 = this.state.cellMap.getOrDefault(State.xy2idx(this.x+2,this.y+2), new Cell("none",-1,-1,0,null,-1));
                        if(c1.color!=this.color){
                            Cell c2 = this.state.cellMap.getOrDefault(State.xy2idx(this.x+1,this.y+1), new Cell("none",-1,-1,0,null,-1));
                            if(c2.color==0){
                                nextCoordList.add(new int[]{this.x+2,this.y+2});
                            }
                        }
                    }
                }

            }else if(this.color==-1){
                if(this.y-2>=0){
                    if(this.x-2>=0){
                        Cell c1 = this.state.cellMap.getOrDefault(State.xy2idx(this.x-2,this.y-2), new Cell("none",-1,-1,0,null,-1));
                        if(c1.color!=this.color){
                            Cell c2 = this.state.cellMap.getOrDefault(State.xy2idx(this.x-1,this.y-1), new Cell("none",-1,-1,0,null,-1));
                            if(c2.color==0){
                                nextCoordList.add(new int[]{this.x-2,this.y-2});
                            }
                        }
                    }
                    if(this.x+2<this.state.boardWidth){
                        Cell c1 = this.state.cellMap.getOrDefault(State.xy2idx(this.x+2,this.y-2), new Cell("none",-1,-1,0,null,-1));
                        if(c1.color!=this.color){
                            Cell c2 = this.state.cellMap.getOrDefault(State.xy2idx(this.x+1,this.y-1), new Cell("none",-1,-1,0,null,-1));
                            if(c2.color==0){
                                nextCoordList.add(new int[]{this.x+2,this.y-2});
                            }
                        }
                    }
                }
                if(this.y+2<5){
                    if(this.x-2>=0){
                        Cell c1 = this.state.cellMap.getOrDefault(State.xy2idx(this.x-2,this.y+2), new Cell("none",-1,-1,0,null,-1));
                        if(c1.color!=this.color){
                            Cell c2 = this.state.cellMap.getOrDefault(State.xy2idx(this.x-1,this.y+1), new Cell("none",-1,-1,0,null,-1));
                            if(c2.color==0){
                                nextCoordList.add(new int[]{this.x-2,this.y+2});
                            }
                        }
                    }
                    if(this.x+2<this.state.boardWidth){
                        Cell c1 = this.state.cellMap.getOrDefault(State.xy2idx(this.x+2,this.y+2), new Cell("none",-1,-1,0,null,-1));
                        if(c1.color!=this.color){
                            Cell c2 = this.state.cellMap.getOrDefault(State.xy2idx(this.x+1,this.y+1), new Cell("none",-1,-1,0,null,-1));
                            if(c2.color==0){
                                nextCoordList.add(new int[]{this.x+2,this.y+2});
                            }
                        }
                    }
                }
            }
        }else if(this.type.equals("shi")){
            if(this.color==1){
                if(this.y-1>6){
                    if(this.x-1>=3){
                        Cell c1 = this.state.cellMap.getOrDefault(State.xy2idx(this.x-1,this.y-1), new Cell("none",-1,-1,0,null,-1));
                        if(c1.color!=this.color){
                            nextCoordList.add(new int[]{this.x-1,this.y-1});
                        }
                    }
                    if(this.x+1<=5){
                        Cell c1 = this.state.cellMap.getOrDefault(State.xy2idx(this.x+1,this.y-1), new Cell("none",-1,-1,0,null,-1));
                        if(c1.color!=this.color){
                            nextCoordList.add(new int[]{this.x+1,this.y-1});
                        }
                    }
                }
                if(this.y+1<this.state.boardHeight){
                    if(this.x-1>=3){
                        Cell c1 = this.state.cellMap.getOrDefault(State.xy2idx(this.x-1,this.y+1), new Cell("none",-1,-1,0,null,-1));
                        if(c1.color!=this.color){
                            nextCoordList.add(new int[]{this.x-1,this.y+1});
                        }
                    }
                    if(this.x+1<=5){
                        Cell c1 = this.state.cellMap.getOrDefault(State.xy2idx(this.x+1,this.y+1), new Cell("none",-1,-1,0,null,-1));
                        if(c1.color!=this.color){
                            nextCoordList.add(new int[]{this.x+1,this.y+1});
                        }
                    }
                }

            }else if(this.color==-1){
                if(this.y-1>=0){
                    if(this.x-1>=3){
                        Cell c1 = this.state.cellMap.getOrDefault(State.xy2idx(this.x-1,this.y-1), new Cell("none",-1,-1,0,null,-1));
                        if(c1.color!=this.color){
                            nextCoordList.add(new int[]{this.x-1,this.y-1});
                        }
                    }
                    if(this.x+1<=5){
                        Cell c1 = this.state.cellMap.getOrDefault(State.xy2idx(this.x+1,this.y-1), new Cell("none",-1,-1,0,null,-1));
                        if(c1.color!=this.color){
                            nextCoordList.add(new int[]{this.x+1,this.y-1});
                        }
                    }
                }
                if(this.y+1<=2){
                    if(this.x-1>=3){
                        Cell c1 = this.state.cellMap.getOrDefault(State.xy2idx(this.x-1,this.y+1), new Cell("none",-1,-1,0,null,-1));
                        if(c1.color!=this.color){
                            nextCoordList.add(new int[]{this.x-1,this.y+1});
                        }
                    }
                    if(this.x+1<=5){
                        Cell c1 = this.state.cellMap.getOrDefault(State.xy2idx(this.x+1,this.y+1), new Cell("none",-1,-1,0,null,-1));
                        if(c1.color!=this.color){
                            nextCoordList.add(new int[]{this.x+1,this.y+1});
                        }
                    }
                }
            }
        }else if(this.type.equals("jiang")){
            if(this.color==1){
                if(this.y-1>=7){
                    Cell c1 = this.state.cellMap.getOrDefault(State.xy2idx(this.x,this.y-1), new Cell("none",-1,-1,0,null,-1));
                    if(c1.color!=this.color){
                        nextCoordList.add(new int[]{this.x,this.y-1});
                    }
                }
                if(this.y+1<this.state.boardHeight){
                    Cell c1 = this.state.cellMap.getOrDefault(State.xy2idx(this.x,this.y+1), new Cell("none",-1,-1,0,null,-1));
                    if(c1.color!=this.color){
                        nextCoordList.add(new int[]{this.x,this.y+1});
                    }
                }

                for (int y = this.y-1; y >= 0; y--) {
                    Cell c = this.state.cellMap.getOrDefault(State.xy2idx(this.x,y), new Cell("none",-1,-1,0,null,-1));
                    if(c.color==this.color){
                        break;
                    }else if(c.color==-this.color){
                        if(c.type.equals("jiang")){
                            nextCoordList.add(new int[]{this.x,y});
                        }
                        break;
                    }
                }
            }else if(this.color==-1){
                if(this.y-1>=0){
                    Cell c1 = this.state.cellMap.getOrDefault(State.xy2idx(this.x,this.y-1), new Cell("none",-1,-1,0,null,-1));
                    if(c1.color!=this.color){
                        nextCoordList.add(new int[]{this.x,this.y-1});
                    }
                }
                if(this.y+1<=2){
                    Cell c1 = this.state.cellMap.getOrDefault(State.xy2idx(this.x,this.y+1), new Cell("none",-1,-1,0,null,-1));
                    if(c1.color!=this.color){
                        nextCoordList.add(new int[]{this.x,this.y+1});
                    }
                }

                for (int y = this.y+1; y < this.state.boardHeight; y++) {
                    Cell c = this.state.cellMap.getOrDefault(State.xy2idx(this.x,y), new Cell("none",-1,-1,0,null,-1));
                    if(c.color==this.color){
                        break;
                    }else if(c.color==-this.color){
                        if(c.type.equals("jiang")){
                            nextCoordList.add(new int[]{this.x,y});
                        }
                        break;
                    }
                }
            }

            if(this.x-1>=3){
                Cell c1 = this.state.cellMap.getOrDefault(State.xy2idx(this.x-1,this.y), new Cell("none",-1,-1,0,null,-1));
                if(c1.color!=this.color){
                    nextCoordList.add(new int[]{this.x-1,this.y});
                }
            }
            if(this.x+1<=5){
                Cell c1 = this.state.cellMap.getOrDefault(State.xy2idx(this.x+1,this.y), new Cell("none",-1,-1,0,null,-1));
                if(c1.color!=this.color){
                    nextCoordList.add(new int[]{this.x+1,this.y});
                }
            }

        }

    }

}

class State{
	public HashMap<Integer, Cell>  cellMap;

	public static int boardWidth = 9;
    public static int boardHeight = 10;
	public Cell lastMove;
	public int result;
	public int winColor = 0;

    State(Cell lastMove) {
        this.cellMap = new HashMap<Integer, Cell>();
        this.lastMove = lastMove;
    }

    public static int xy2idx(int x, int y){
        return y* State.boardWidth+x;
    }

    public static int[] idx2xy(int idx){
        int x = idx%State.boardWidth;
        int y = (idx-x)/State.boardWidth;
        return new int[]{x,y};
    }

    public State clone(){
        State state = new State(this.lastMove.clone());

        HashMap<Integer, Cell> cellMap = new HashMap<Integer, Cell>();
		this.cellMap.forEach((key, value) -> {
		    Cell c1 = value.clone();
            c1.state = state;
            cellMap.put(key, c1);
        });
        state.cellMap = cellMap;
        state.winColor = this.winColor;

        return state;

    }

    public Cell checkPiece(Cell cell,int x,int y){
        Cell res = new Cell("illegal",-1,-1,0,null,-1);
        for (int i = 0; i < cell.nextCoordList.size(); i++) {
            int[] coord = cell.nextCoordList.get(i);
            if(coord[0]==x&&coord[1]==y){
                Cell c = this.cellMap.getOrDefault(this.xy2idx(x,y), new Cell("none",x,y,0,null,this.xy2idx(x,y)));
                if(c.color!=cell.color){
                    return c;
                }
            }
        }
        return res;
    }

    public void placePiece(Cell cell,int x,int y){

        if(cellMap.containsKey(this.xy2idx(x,y))){
            if(cellMap.get(this.xy2idx(x,y)).type.equals("jiang")){
                this.winColor = cell.color;
            }
        }

        cellMap.put(this.xy2idx(x,y),cell);
        cellMap.remove(cell.idx);
        cell.x = x;
        cell.y = y;
        cell.idx = this.xy2idx(x,y);

        this.cellMap.forEach((idx, cell0)->{
            cell0.initNextCoordList();
        });

        this.lastMove = cell;



    }

    public int getLocalScore() {
        AtomicInteger score = new AtomicInteger();
        this.cellMap.forEach((idx, cell)->{
            if(cell.color==-1){
                score.addAndGet(cell.score);
                score.addAndGet(cell.getPositionScore());
            }else if(cell.color==1){
                score.addAndGet(-cell.score);
                score.addAndGet(-cell.getPositionScore());
            }
        });

        return score.get();
    }
}

class Node  implements Callable<Integer> {
    public Node father = null;
    public float ucb;
    public int Q;
    public int N;
    public ArrayList<Node> children;
    public Node maxUCBChild;
    public State state;
    public boolean end;
    public int winColor = 0;
    public int runTime = 3000;
    public Node bestChild;
    public int localScore;
    public static int JiangScore = 1000000000;
    public int score;
    public int floor = 0;

    Node(Node father, State state) {
        this.father = father;
        this.ucb = -Float.MAX_VALUE;
        this.Q = 0;
        this.N = 0;
        this.children = new ArrayList<Node>();
        this.maxUCBChild = null;
        this.state = state;
        this.end = false;
    }

    public Node clone() {
        Node node = new Node(this.father, this.state.clone());
        node.ucb = this.ucb;
        node.ucb = this.ucb;
        node.Q = this.Q;
        node.N = this.N;
        node.winColor = this.winColor;
        node.maxUCBChild = this.maxUCBChild;
        node.end = this.end;
        node.runTime = this.runTime;
        node.children = new ArrayList<Node>();
        for (Node child : this.children) {
            node.children.add(child.clone());
        }
        return node;
    }

    public int getWinColor(State state) {
//        AtomicInteger black = new AtomicInteger();
//        AtomicInteger white = new AtomicInteger();
//
//        state.cellMap.forEach((idx, color) -> {
//            if(color==1){
//                black.getAndIncrement();
//            }else if(color==-1){
//                white.getAndIncrement();
//            }
//        });
//
//        if(black.get() > white.get()){
//            return 1;
//        }else if(black.get() < white.get()){
//            return -1;
//        }else {
//            return 0;
//        }

        return 0;
    }

    public Node getChild(int x, int y) {
        for (int idx = 0; idx < this.children.size(); idx++) {
            Cell lastMove = this.children.get(idx).state.lastMove;
            if (lastMove.x == x && lastMove.y == y) {
                return this.children.get(idx);
            }
        }
        return null;
    }

    public void getLocalScore() {
        this.localScore = this.state.getLocalScore();
    }

    public int  getScoreMultithreading(){

        for(Cell cell: this.state.cellMap.values()) {
            if (cell.color == -this.state.lastMove.color) {
                for (int i = 0; i < cell.nextCoordList.size(); i++) {
                    State state1 = this.state.clone();
                    int[] coord = cell.nextCoordList.get(i);
                    Cell cell1 = state1.cellMap.get(cell.idx);
                    state1.placePiece(cell1, coord[0], coord[1]);
                    Node child = new Node(null, state1);
                    child.floor = 0;
                    this.children.add(child);
                }
            }
        }
        ExecutorService executorService = Executors.newFixedThreadPool(this.children.size());
        List<Future<Integer>> futureList = new ArrayList<>();
        for (int i = 0; i < this.children.size(); i++) {
            Node item = this.children.get(i);
            Future<Integer> future = executorService.submit(item);
            futureList.add(future);
        }
        for (Future<Integer> future1 : futureList) {
            try {
                future1.get();
            } catch (InterruptedException | ExecutionException e) {
                e.printStackTrace();
            }
        }
        executorService.shutdown();

        this.bestChild = this.children.get(0);
        if (this.state.lastMove.color == 1) {
            for (int i = 0; i < this.children.size(); i++) {
                Node child = this.children.get(i);
                if (child.score > this.bestChild.score) {
                    this.bestChild = child;
                }
            }
        } else if (this.state.lastMove.color == -1) {
            for (int i = 0; i < this.children.size(); i++) {
                Node child = this.children.get(i);
                if (child.score < this.bestChild.score) {
                    this.bestChild = child;
                }
            }
        }

        this.score = this.bestChild.score;
        return this.score;
    }

    public int getScore(int depth) {
        this.getLocalScore();
        if (Math.abs(this.localScore) > Node.JiangScore / 2) {
            this.score = this.localScore;
            this.winColor = this.localScore>0?-1:1;
            return this.score;
        }
        if (this.floor == depth) {
            this.score = this.localScore;
            return this.score;
        } else {
            boolean findCut = false;

            for(Cell cell: this.state.cellMap.values()) {

                if(findCut){
                    break;
                }

                if(cell.color==-this.state.lastMove.color){

                    int floor = this.floor + 1;

                    for (int i = 0; i < cell.nextCoordList.size(); i++) {

                        if(findCut){
                            break;
                        }

                        State state1 = this.state.clone();
                        int[] coord = cell.nextCoordList.get(i);
                        Cell cell1 = state1.cellMap.get(cell.idx);
                        state1.placePiece(cell1, coord[0], coord[1]);
                        Node child = new Node(this,state1);
                        child.floor = floor;
                        this.children.add(child);
                        child.getScore(depth);

                        if (this.children.size() == 1) {
                            this.bestChild = child;
                        } else {
                            if (this.state.lastMove.color == 1) {
                                if (child.score > this.bestChild.score) {
                                    this.bestChild = child;
                                }
                            } else if (this.state.lastMove.color == -1) {
                                if (child.score < this.bestChild.score) {
                                    this.bestChild = child;
                                }
                            }
                        }

                        if (this.father!=null && this.father.children.size() > 1) {
                            if (this.state.lastMove.color == 1) {
                                if (child.score > this.father.bestChild.score) {
                                    findCut = true;
                                    break;
                                }
                            } else if (this.state.lastMove.color == -1) {
                                if (child.score < this.father.bestChild.score) {
                                    findCut = true;
                                    break;
                                }
                            }
                        }

                    }



                }
            }

            this.score = this.bestChild.score;
        }

        return this.score;
    }

    @Override
    public Integer call(){
        this.getScore(2);
        return 1;
    }
}


